package com.backpack;

/**
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 */
public class CoinChangeII0112_518 {
    public int change(int amount, int[] coins) {
        //完全背包问题
        //dp[i] 表示 容量总金额为i的背包 有dp[i]种方法
        int[] dp = new int[amount + 1];

        //初始化
        dp[0] = 1;

        //递归公式： dp[j] += dp[j-coins[i]];
        //完全背包 遍历顺序：先遍历物品（正序），再遍历背包(正序)
        for (int i = 0; i < coins.length ; i++) { //物品
            for (int j = coins[i]; j <= amount ; j++) { //背包
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}
